package com.lw.leetcode.node;

/**
 * 面试题 04.02. 最小高度树
 * leetcode 108. 将有序数组转换为二叉搜索树
 *
 * @Author liw
 * @Date 2021/4/16 10:18
 * @Version 1.0
 */
public class SortedArrayToBST {

    public static void main(String[] args) {

        int[] arr = {-10, -3, 0, 5, 9};
        TreeNode treeNode = new SortedArrayToBST().sortedArrayToBST(arr);
        System.out.println(treeNode);

    }


    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        int length = nums.length;
        int st = 0;
        int end = length - 1;
        int m = st + ((end - st) >> 1);
        TreeNode root = new TreeNode(nums[m]);
        adjust(nums, root, st, end, m);
        return root;
    }

    /**
     * 调整
     *
     * @param nums 数组
     * @param node 节点
     * @param st   数组开始索引
     * @param end  数组结束索引
     * @param m    中点
     */
    private static void adjust(int[] nums, TreeNode node, int st, int end, int m) {
        if (st > end) {
            return;
        }
        int l = st + ((m - 1 - st) >> 1);
        int r = m + 1 + ((end - 1 - m) >> 1);
        if (l >= st) {
            node.left = new TreeNode(nums[l]);
            adjust(nums, node.left, st, m - 1, l);
        }
        if (r >= m + 1 && r <= end) {
            node.right = new TreeNode(nums[r]);
            adjust(nums, node.right, m + 1, end, r);
        }
    }


}
